/**
 * 堆是一颗完全二叉树
 * [10 9 8 5 6 7 4 3]
 * 10 0 【1,2】
 * 9 1 【3,4】
 * 8 2 【5,6】
 * 完全二叉树，除叶子层都是满节点
 * 第i个节点  2*i+1
 * 1. 左子树节点的位置  2*i+1
 * 2. 右子树节点的位置  2*i+2
 * 3. 父节点的位置
 *  (i-1)/2
 */
import { ICompareFunction,defaultCompare, Compare } from "../../util/util";

export class MinHeap<T>{
    protected heap:T[];
    constructor(protected compareFn:ICompareFunction<T>=defaultCompare){
        this.heap=[];
    }
    protected getLeftIndex(index:number):number{
        return 2*index+1;
    }
    protected getRightIndex(index:number):number{
        return 2*index+2;
    }
    protected getParentIndex(index:number):number|undefined{
        if(index==0){
            return undefined;
        }
        return Math.floor((index-1)/2);
    }
    insert(value:T){
        if(value!=null){
            // 先放到最后面
            // 违反堆的定义
            this.heap.push(value);
            this.shiftUp(this.heap.length-1);
            return true;
        }
        return false;
    }
    protected shiftUp(index:number):void{
        let parent = <number>this.getParentIndex(index);
        while(index>0 && this.compareFn(this.heap[parent],this.heap[index])===Compare.BIGGER_THEN){
            this.swap(this.heap,parent,index);
            // 循环一直执行
            index=parent;
            parent=<number>this.getParentIndex(index);
        }
    }
    protected swap(array:T[],exchangeElement:number,exchangedElement:number):void{
        const temp=array[exchangeElement];
        array[exchangeElement]=array[exchangedElement];
        array[exchangedElement]=temp;
    }
    getIsArray():T[]{
        return this.heap;
    }
    finMininum():T|undefined{
        return this.isEmpty()?undefined:this.heap[0]
    }
    isEmpty():boolean{
        return this.size()===0
    }
    size(){
        return this.heap.length
    }
}

export class MaxHeap<T> extends MinHeap<T>{
    constructor(){
        super()
    }
}